//在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。 
//
// 如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求： 
//
// 
// ages[y] <= 0.5 * ages[x] + 7 
// ages[y] > ages[x] 
// ages[y] > 100 && ages[x] < 100 
// 
//
// 否则，x 将会向 y 发送一条好友请求。 
//
// 注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。 
//
// 返回在该社交媒体网站上产生的好友请求总数。 
//
// 
//
// 示例 1： 
//
// 
//输入：ages = [16,16]
//输出：2
//解释：2 人互发好友请求。
// 
//
// 示例 2： 
//
// 
//输入：ages = [16,17,18]
//输出：2
//解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
// 
//
// 示例 3： 
//
// 
//输入：ages = [20,30,100,110,120]
//输出：3
//解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。
// 
//
// 
//
// 提示： 
//
// 
// n == ages.length 
// 1 <= n <= 2 * 10⁴ 
// 1 <= ages[i] <= 120 
// 
//
// Related Topics 数组 双指针 二分查找 排序 👍 247 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-11-17 22:29:16
 * @description 825.适龄的朋友
 */
public class FriendsOfAppropriateAges{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FriendsOfAppropriateAges fun=new FriendsOfAppropriateAges();
	 	 Solution solution = fun.new Solution();
			solution.numFriendRequests(new int[]{118,14,7,63,103});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * 1.遍历所有
		 * 2.排序二分，只需要找他左边的最小,
		 * */
    public int numFriendRequests(int[] ages) {
        int res=0;
		Arrays.sort(ages);
		for (int i = ages.length-1; i >0; i--) {
			double min=ages[i]*0.5+7;
			int l=0,r=i-1;
			while (l<r){
				int m=l+(r-l)/2;
				if(ages[m]>min){
					r=m;
				}else {
					l=m+1;
				}
			}
			//如果没找到就跳过
			if(ages[l]<=min) continue;
			int k=i;
			//如果有多个年龄一样的，他们的结果是一样的，所以排序后倒序找
			while (i>0&&ages[i]==ages[i-1]) {
				i--;
				res+=k-l;
			}
			res+=k-l;
		}
		return res;

    }
		//双指针
	  public int numFriendRequests1(int[] ages) {
        int n = ages.length;
        Arrays.sort(ages);
        int left = 0, right = 0, ans = 0;
        for (int age : ages) {
			//第二个条件，其实14和以下的永远不能发起聊天
            if (age < 15) {
                continue;
            }
			//因为总的年龄是排序的，所以维护的左右指针一定对后面的也有用
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }
            ans += right - left;
        }
        return ans;
    }
	//计数排序，

	public int numFriendRequests2(int[] ages) {
        int[] cnt = new int[121];
		//先计数每个年龄的个数
        for (int age : ages) {
            ++cnt[age];
        }
		//然后对前面的前缀和，其中pre[i]表示0~i有多少人
        int[] pre = new int[121];
        for (int i = 1; i <= 120; ++i) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int ans = 0;
		//直接从15岁开始
        for (int i = 15; i <= 120; ++i) {
			//如果这个年龄有人
            if (cnt[i] > 0) {
				//取出符合这个年龄的最小年龄
                int bound = (int) (i * 0.5 + 8);
				//当前年龄有多少人 * 前面符合区间有多少人就是这个年龄所有人可以发起的数量
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}
